package com.datastructure.test.plusonetolistnode;

import java.util.LinkedList;
import java.util.List;

public class PlusOneToListNode {

    public static void main(String[] args) {
        PlusOneToListNode plusOneToListNode = new PlusOneToListNode();
        ListNode head = new ListNode(9);
        head.next=new ListNode(9);
        head.next.next=new ListNode(9);
        ListNode listNode = plusOneToListNode.plusOne(head);
        System.out.println(listNode);
    }

    public ListNode plusOne (ListNode head) {
        // write code here
        if(head==null){
            return head;
        }
        int carry = 1;
        head = reverseListNode(head);
        ListNode cur;
        ListNode res = null;
        while (head!=null){
            int sum = head.val+carry;
            cur = new ListNode(sum%10);
            cur.next=res;
            res = cur;
            carry=sum/10;
            head=head.next;
        }
        if(carry==1){
            ListNode result = new ListNode(1);
            result.next=res;
            return result;
        } else {
            return res;
        }
    }

    public ListNode reverseListNode(ListNode head){
        ListNode cur = head;
        ListNode res = null;
        while (cur!=null){
            ListNode temp = cur.next;
            cur.next=res;
            res = cur;
            cur=temp;
        }
        return res;
    }
}

class ListNode {
   int val;
   ListNode next = null;
   public ListNode(int val) {
     this.val = val;
   }
 }